package 简单.二分查找;

/**
 * 实现 int sqrt(int x) 函数。
 * <p>
 * 计算并返回 x 的平方根，其中 x 是非负整数。
 * <p>
 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去
 * <p>
 * 来源：https://leetcode-cn.com/problems/sqrtx/submissions/
 */
public class x的平方根_69 {

    public static void main(String[] args) {

        System.out.println(Integer.MAX_VALUE);
        int i = efficientMySqrt(2147483646);
        System.out.println(i);
    }

    //使用开根号函数sqrt()
    public static int mySqrt1(int x) {

        double sqrt = Math.sqrt(x);
        return (int) sqrt;

    }

    //exp() 方法用于返回自然数底数e的参数次方,log() 方法用于返回参数的自然数底数的对数值。
    //根号下x = x 1/2 = (e lnx) 1/2 = e（0.5*lnx）
    public static int mySqrt2(int x) {
        //为0直接返回
        if (x == 0) {
            return 0;
        }
        //可能有1的偏差
        int sqrt = (int) Math.exp(0.5 * Math.log(x));
        //int的最大值为2147483647,如果参数为2147483647，则永远小于，需要将相乘得到的数转成long
        return (long) (sqrt + 1) * (sqrt + 1) <= x ? sqrt + 1 : sqrt;
    }

    //二分查找法：满足K的平方 < = x 的K最大值
    public static int efficientMySqrt(int x) {
        int left = 0;
        int right = x;
        int sqrt = -1;
        while (right >= left) {
            int mid = left + (right - left) / 2;
            //mid*mid会超过int的最大值，需要转成long类型
            if ((long) mid * mid <= x) {
                sqrt = mid;
                //取小于x中sqrt的最大值
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return sqrt;
    }

}
